package seqlist.oj;

/**
 * 以x为基准分割链表
 */
public class Num0204 {
    public ListNode partition(ListNode head, int x) {
        // 创建small和big两个小链表的头节点
        ListNode smallHead = new ListNode(-1);
        ListNode bigHead = new ListNode(-1);
        // 按照升序插入，因此需要尾插
        // 分别指向两个子链表的尾部
        ListNode smallTail = smallHead;
        ListNode bigTail = bigHead;
        // 边遍历原链表，根据值将节点依次放在两个子链表中
        while (head != null) {
            if (head.val < x) {
                // 放在small链表中
                smallTail.next = head;
                smallTail = head;
            }else {
                // 此时head.val >= x,放在big链表中
                bigTail.next = head;
                bigTail = head;
            }
            head = head.next;
        }
        // 将bigTail尾部的元素置为null
        bigTail.next = null;
        // 拼接小链表与大链表
        smallTail.next = bigHead.next;
        return smallHead.next;
    }
}
